import java.util.Stack;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 07 - 17
 * Time: 18:42
 */
//分三种情况
//法一
public class Solution7 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null) {//递归过程中变的是root，p和q是不会变的
                return null;
            }
            if(p == root || q == root) {
                return root;//这个root是最近公共祖先
            }
            TreeNode leftTreeSeek = lowestCommonAncestor(root.left, p, q);
            TreeNode rightTreeSeek = lowestCommonAncestor(root.right, p, q);
            if(leftTreeSeek != null && rightTreeSeek != null) {
                return root;
            }
            if(leftTreeSeek != null) {
                return leftTreeSeek;
            }
            return rightTreeSeek;
        }
}

//法二
class Solution8 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        Stack<TreeNode> stackp = new Stack<>();
        Stack<TreeNode> stackq = new Stack<>();
        getPath(root, p, stackp);
        getPath(root, q, stackq);
        int sizep = stackp.size();
        int sizeq = stackq.size();
        if(sizep > sizeq) {
            int size = sizep - sizeq;
            while(size != 0) {
                stackp.pop();
                size--;
            }
        }else {
            int size = sizeq - sizep;
            while(size != 0) {
                stackq.pop();
                size--;
            }
        }
        while(!stackq.isEmpty()) {
            if(stackp.peek().equals(stackq.peek())) {
                return stackp.peek();
            }
            stackp.pop();
            stackq.pop();
        }
        return null;
    }
    boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if(root == null || node == null) {
            return false;
        }
        stack.push(root);
        if(root == node) {
            return true;
        }

        boolean flg1 = getPath(root.left, node, stack);
        if(flg1) {
            return true;
        }
        boolean flg2 = getPath(root.right, node, stack);
        if(flg2) {
            return true;
        }
        stack.pop();
        return false;
    }
}

